#include <stdio.h>

int searchInsert(int *nums,int numsSize,int target)
{
    if(target <= nums[0])
    {
        return 0;
    }
    if(target > nums[numsSize - 1])
    {
        return numsSize;
    }
    int left = 0;
    int right = numsSize - 1;
    int mid = left + (right - left) / 2;
    int ret;
    while(left <= right)
    {
        if(nums[mid] < target)
            left = mid + 1;
        else if(nums[mid] > target)
            right = mid - 1;
        else if(nums[mid] == target)
            return mid;
        mid = left + (right - left) / 2;
    }
    return mid;
}

int main()
{
    int nums[] = {1,3,5,6};
    int target = 9;
    int ret = searchInsert(nums,sizeof(nums)/sizeof(nums[0]),target);
    printf("ret = %d\n",ret);
    return 0;
}